#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
struct myNode
{
    int depth;
    Node *node;
    myNode(Node *node, int depth = 0) : node(node), depth(depth){};
};
queue<myNode> que;
class Solution
{
public:
    Node *connect(Node *root)
    {
        Node *_hotNode = nullptr;
        int _hotDepth = 0;
        que.emplace(root, 0);
        while (que.empty() == false)
        {
            myNode nd = que.front();
            que.pop();
            if (nd.node == nullptr)
                continue;
            if (nd.depth > _hotDepth)
            {
                _hotDepth++;
            }
            else
            {
                if (_hotNode != nullptr)
                    _hotNode->next = nd.node;
            }
            _hotNode = nd.node;
            que.emplace(nd.node->left, nd.depth + 1);
            que.emplace(nd.node->right, nd.depth + 1);
        }
        return root;
    }
};